#include "scan.h"
#include "limits.h"
#include "global.h"

pthread_mutex_t lock;
pthread_barrier_t barrier;

class Prefix: public Scanner<int, int>
{
public:
  int init() { return 0;}
  int accum(int t, int d) { return t+d;}
  int combine(int left, int right) { return left+right;}
  int scan(int t, int not_used) { return t;}
  Prefix(int* data, int* result, INDEX length)
    : Scanner<int, int>(data, result, length) {}
};

int main() {
  int* data = (int*) new int [INPUT_SIZE];
  int* result = (int*) new int [INPUT_SIZE];
  int* histogram = (int*) new int [INPUT_RANGE];
  int* starting_index = (int*) new int [INPUT_RANGE+1];

  // generate the input
  for(INDEX i=0; i<INPUT_SIZE; i++)
    data[i] = rand()%INPUT_RANGE;

  // initialize the histogram
  for(INDEX i=0; i<INPUT_RANGE; i++)
    histogram[i] = 0;
  starting_index[0] = 0;

  // calculate the historgram
  // TODO: use reduce for histogram?
  for(INDEX i=0; i<INPUT_SIZE; i++)
    histogram[data[i]]++;

  // calculate the start index for each key
  Prefix prefix(histogram, starting_index+1, INPUT_RANGE);
  prefix.Start();

  // sort input data;
  // TODO: parallelize this part as well?
  for(INDEX i=0; i<INPUT_SIZE; i++) {
    result[starting_index[data[i]]] = data[i];
    starting_index[data[i]] ++;
  }

  // check result
  for(INDEX i=0; i<INPUT_SIZE; i++) {
    bool f = 0;
    INDEX j;
    for(j=0; j<INPUT_SIZE; j++) {
      if(data[j] == result[i]) {
        f = 1;
        break;
      }
    }
    if (f!=1) {
      cout<<result[i]<<" "<<i<<endl;
      assert(f==1);
    }
  }

  cout<<endl<<"sort succeeded"<<endl;

  pthread_exit(NULL);
}
